package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description: 乘积最大子数组
 * 152 maximum-product-subarray
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class MaximumProductSubarray {
    public static void main(String[] args) {
//        int[] nums = {2,3,-2,2,4};
        int[] nums = {2, 3, -2, -2, 10};
        Solution solution = new MaximumProductSubarray().new Solution();
        System.out.println(solution.maxProduct(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * 思路： 求最大值，可以看成求被0拆分的各个子数组的最大值。
         * <p>
         * 当一个数组中没有0存在，则分为两种情况：
         * <p>
         * 1.负数为偶数个，则整个数组的各个值相乘为最大值；
         * <p>
         * 2.负数为奇数个，则从左边开始，乘到最后一个负数停止有一个“最大值”，从右边也有一个“最大值”，比较，得出最大值。
         *
         * @param nums
         * @return
         */
        public int maxProduct(int[] nums) {
            int a = 1;
            int max = nums[0];

            for (int num : nums) {
                a = a * num;
                if (max < a) {
                    max = a;
                }
                if (num == 0) {
                    a = 1;
                }

            }
            a = 1;
            for (int i = nums.length - 1; i >= 0; i--) {
                a = a * nums[i];
                if (max < a) {
                    max = a;
                }
                if (nums[i] == 0) {
                    a = 1;
                }
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
